class Solution {
    int _n, _k;
    vector<int> path;
    vector<vector<int>> ret;
public:
    vector<vector<int>> combine(int n, int k) {
        _n = n;
        _k = k;
        dfs(1);
        return ret;
    }
 
    void dfs(int pos)
    {
        if(path.size() == _k)
        {
            ret.push_back(path);
            return;
        }
 
        for(int i = pos; i <= _n; ++i) // 剪枝
        {
            path.push_back(i);
            dfs(i + 1);
            path.pop_back(); // 恢复现场
        }
    }
};